using namespace std;

template <typename Comparable>
class RedBlackTree
{
private:
    struct RedBlackNode
    {
        Comparable element;
        RedBlackNode * left;
        RedBlackNode * right;
        int color;

        RedBlackNode(const & theElement = Comparable{}, RedBlackNode *lt = nullptr, RedBlackNode *rt = nullptr, int c = BLACK) : element{theElement}, left{lt}, right{rt}, color{c}
        {}
        /*右值版本*/
    };
    
    //树的头节点（包括negInf）
    RedBlackNode *header;
    RedBlackNode *nullNode;

    //用于insert例程和其辅助对象（逻辑上是静态的）
    RedBlackNode *current;
    RedBlackNode *parent;
    RedBlackNode *grand;
    RedBlackNode *great;
    //通常是递归的过程
    void reclaimMemory(RedBlackNode *t)
    void printTree(RedBlackNode *t) const
    {
        if(t != t->left)
        {
            printTree(t->left);
            cout << t->element << endl;
            printTree(t->right);
        }
    }

    /*克隆操作*/
    RedBlackNode * clone(RedBlackNode *t) const
    {
        if(t == t->left) //不能对nullNode测试
            return nullNode;
        else
            return new RedBlackNode { t->element, clone(t->left), clone(t->right), t->color };
    }
    
    /*红黑树操作*/
    void handleReorient(const Comparable & item)
    {
        //颜色翻转
        current->color = RED;
        current->left->color = BLACK;
        current->right->color = BLACK;

        if(parent->color == RED)
        {
            grand->color = RED;
            if(item < grand->element != item < parent->element)
                parent = rotate(item,grand); //开始双旋转
            current = rotate(item,great);
            current->color = BLACK;
        }
        header->right->color = BLACK;   //使根呈黑色
    }
    /* 单旋转或双旋转的内部例程
     * 因为结果被附接到父节点上，有四种情况
     * 1.通过handleReorient被调用
     * 2.item是handleReorient中的item
     * 3.theParent是所旋转子树的根的父节点
     * 4.返回旋转子树的根
    */ 
    RedBlackNode * rotate(const Comparable& item, RedBlackNode *theParent)
    {
        if(item < theParent->element)
        {
            item < theParent->left->element ?
                rotateWithLeftChild(theParent->left) : //LL
                rotateWithRightChild(theParent->left); //LR
            return theParent->left;
        }
        else
        {
            item < theParent->right->element ?
                rotateWithLeftChild(theParent->right) : //RL
                rotateWithRightChild(theParent->right); //RR
            return theParent->right;
        }
        
    }
    void rotateWithLeftChild(RedBlackNode *& k2)
    void rotateWithRightChild(RedBlackNode *& k1)

public:
    //显式构造函数，其中negInf是小于或等于所有其它项的某个值
    explicit RedBlackTree(const Comparable & negInf)
    {
        nullNode = new RedBlackNode;
        nullNode->left = nullNode->right = nullNode;

        header = new RedBlackNode(negInf);
        header->left = header->right = nullNode;
    }
    /*含参构造函数*/
    RedBlackTree(const RedBlackTree & rhs)
    {
        nullNode = new RedBlackNode;
        nullNode->left = nullNode->right = nullNode;

        header = new RedBlackNode {rhs.header->element};
        header->left = nullNode;
        header->right =  clone(rhs.header->right);
    }
    
    //右值构造函数
    /*析构函数*/
    ~RedBlackTree();

    /*查找功能*/
    const Comparable & findMin() const
    const Comparable & findMax() const
    bool contains(const Comparable & x) const
    bool isEmpty() const
    /*打印树*/
    void printTree() const
    {
        if(header->right == nullNode)
            cout << "是空树" << endl;
        else
            printTree(header->right);
    }

    /*增删功能*/
    void makeEmpty()
    void insert(const Comparable & x)
    {
        current = parent = grand = header;
        nullNode->element = x;

        while(current->element != x)
        {
            great = grand; grand = parent; parent = current;
            current = (x < current->element ? current->left : current->right);

            //检测是否两个红儿子，若是，则调整
            if(current->left->color == RED && current->right->color == RED)
                handleReorient(x);
        }
        
        //若节点已经存在，则插入失败
        if(current != nullNode)
            return;
        current = new RedBlackNode {x,nullNode,nullNode};

        //附接到父节点上
        if(x < parent->element)
            parent->left = current;
        else
            parent->right = current;
        handleReorient(x);
    }
    void remove(const Comparable & x)

    /*红黑性质*/
    enum {RED,BLACK};

    /*运算符重载（左右值）*/
    RedBlackTree & operator= (const RedBlackTree & rhs)
    RedBlackTree & operator= (RedBlackTree && rhs)
};
